1. Field of the Invention
This invention relates to the compression and decompression of signals and, more particularly, to ordering and formatting digital information signals while compressing the digital signals, for example, so that, when transmitted over a communications channel or when recorded on a recording medium, the compressed signals can be transmitted or stored in whatever space is allotted for them and so that the signals can be decompressed in such a manner that information can be reconstructed from complete or incomplete segments of the decompressed signals. Here, the information signals are illustratively disclosed in terms of being digital data image signals.
2. Description of Related Art
Reasons for compressing signals such as signals representing images include (a) being able to send a minimal amount of data from one point to another point by way of a communications channel or (b) being able to record a minimal amount of data on a storage medium. One way to achieve the goal of compressing signals is to eliminate the transmission of unnecessary or redundant data. For example, images like digital video images, by their very nature, contain a great deal of redundancy and thus are good candidates for data compression. By removing a portion of the redundancy from a digital image signal at a transmitter, the amount of data either (a) transmitted over a communications channel or (b) recorded on a storage medium may be substantially reduced. The image may then be reconstructed by reintroducing the redundancy (a), if transmitted, at a receiver or (b), if recorded, in the recorder playback electronics.
Data compression for use in conjunction with digital video tape recorders has several unique requirements which impose additional and unusual constraints on any compression methodology used. The unusual constraints generally arise from the typical modes of use of a video tape recorder and from the fact that image data is typically stored on a recording medium like magnetic tape for later use as opposed, for example, to being immediately transmitted to a home viewer. (The term or expression "image data" as used herein refers to data or information defining an image to be displayed.) It is a common requirement in the television industry that a video tape recorder be structured so as to allow editing of the recorded information. Practically, this usually means that the stored data for one field of a two field television frame either occupy an integer number of tracks on the tape or occupy defined image blocks of video data at predictable locations or tracks on the tape. This imposes as a constraint that a field of data or an image block of data be constant in length. Such a seemingly simple constraint places a severe design requirement on any compression scheme because most images statistically have nonuniform probability density functions. One design solution to a digital signal having varying information content would be to allow the encoded data rate to temporally vary on a frame-by-frame or field-by-field basis according to the image content. However, because of editing requirements, the encoded data rate is typically fixed at the upper bound of the channel data rate rather than being allowed to vary.
Various digital video compression studies have recently focused on the two-dimensional discrete cosine transform ("dct") for use as a preferred adaptive coding vehicle due to its energy compaction properties and due to the relative ease with which the dct can be implemented using digital circuits. See, for example, the article by N. Ahmed et al. entitled "Discrete Cosine Transform," IEEE Transaction on Computers, Vol. C-23, No. 1 (January 1974), pp. 90-93. To perform a transformation on a video image, the image is first divided into image blocks of pixels (for example, each block being a square array having, in one case, 16 rows.times.16 columns of pixels or, in another case, 8 rows.times.8 columns of pixels), and then cosine transformed into a set of transform coefficients. (The word "pixel" is a shortened form of the expression "picture element.") In the cosine transformed domain, the larger amplitude coefficients are generally concentrated at the lower frequency components--meaning that the lower frequency components including the zero frequency, or direct current ("dc"), component tend to have the larger amplitude coefficients while many of the higher frequencies tend to have amplitude coefficients of zero or nearly zero values.
Compression can be achieved by scaling, or quantizing, the values of the dct coefficients and then encoding the quantized dct coefficients using an entropy coder such as a Huffman coder. A key factor in making this scheme work effectively is the quantizing process. If the quantization is too fine, the data generated by a Huffman coder will exceed the data rate of the channel (or of the recorder, as the case may be), while if the quantization is too coarse the quantization results in unacceptable distortion or noise. One technique for determining a suitable quantization parameter is one that monitors an output buffer memory and uses a feedback scheme for adjusting the quantization level to maintain an equilibrium of data in the buffer. See, for example, the method described in the article by W-H Chen and W. K. Pratt, "Scene Adaptive Coder," IEEE Transactions on Communications, Vol. Com-32, No. 3 (March 1984), pp 225-232. See also, for example, U.S. Pat. No. 4,302,775. Further, bit allocation methods as utilized in the past do not produce the image quality that is desired if there is a relatively wide range of different kinds of images defined by the data to be compressed. For a dct solution to this problem, see copending patent application Ser. No. 08/106,968 filed Aug. 16, 1993 which is a continuation of Ser. No. 07/654,710 filed Feb. 13, 1991 by Peter Smidth et al. and entitled "Method and Apparatus for Shuffling and Decompressing Data" and assigned to the assignee of this application.
As suggested earlier, an editing feature in a recorder places additional constraints on a data compression methodology. For example, in an edit mode, recorded information is replaced, typically by being overwritten with new information during the course of an edit. That constraint requires that the smallest unit of information that is to be replaced be allotted a fixed space in the recorded data format. For example, when dealing with television signals, the smallest unit of information that is to be replaced would typically be a single field. Allotting a fixed space for a single field is equivalent to allowing any unit of a video signal to be replaced with any equal sized unit of the same video signal or with any equal sized unit of a different video signal. To maintain maximum efficiency in recording and to minimize gaps for record over-runs, it is desirable to use a recording format which has a fixed short period relative to the original uncompressed information. This simplifies the design of a data de-formatter by providing a regular and an expected structure to the data stream received from the communications channel or recovered from storage medium tape. This regular structure allows "intelligent" de-formatting of the image data because certain patterns may be identified as errors and ignored.
Editing also involves relatively high transport speeds. For example, the needs of the television broadcast industry usually demand that video tape recorders allow images to be reproduced at higher than normal record/playback tape transport speeds, which is sometimes referred to in the industry as a picture-in-shuttle mode. It is not uncommon that a picture-in-shuttle mode operate at sixty (60) times the normal playback speed. As a result of the exceedingly high picture-in-shuttle playback speeds, only a fraction, or a portion, of the data recorded on a track is generally recovered. This fact requires that the compressed data which is recorded on the tape be stored in small, yet complete, segments of information from which a portion or portions of the picture may be recovered. The portion that is recovered is sometimes called a "snatch" in the industry. The term "snatch" reflects the fact that, in an attempt to quickly recover all of the information that defines an image to be displayed, the practical result is that some, but not necessarily all, of the information which defines the image is recovered.
One problem then is to order and to format the image data that is being transmitted or that is to be stored on the recording medium in such a manner that the information represented by a snatch can be used to reconstruct a partial, yet recognizable, image from less than all the digital information that defines the image to be displayed. It is further desirable that the reconstruction of the partial image be done in a timely manner and in a manner that permits efficient editing of the information transmitted over a channel or stored on a recording medium, especially in a picture-in-shuttle mode.